// https://www.lintcode.com/problem/median/description
// 描述
// 给定一个未排序的整数数组，找到其中位数。

// 中位数是排序后数组的中间值，如果数组的个数是偶数个，则返回排序后数组的第N/2个数。

// 法一：partition O(N)
class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: An integer denotes the middle number of the array
     */
    void partition(vector<int> &nums, int start, int end, int k) {
        int low = start;
        int high = end;
        int mid = (high - low) / 2 + low;
        int p = nums[mid];
        while (low < high) {
            while (nums[low] < p) low++;
            while (nums[high] > p) high--;
            if (low <= high) {
                swap(nums[low++], nums[high--]);
            }
        }
        // if (low < end && k > low) partition(nums, low, end, k);
        // if (high > start && k < high) partition(nums, start, high, k);
        if (low < end && k >= low) partition(nums, low, end, k);
        if (high > start && k <= high) partition(nums, start, high, k);
    }
    int median(vector<int> &nums) {
        int k = (nums.size() - 1) / 2;
        int start = 0;
        int end = nums.size() - 1;
        partition(nums, start, end, k);
        return nums[k];        
    }
};

// 法二：priority_queue O(N)
class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: An integer denotes the middle number of the array
     */
    int median(vector<int> &nums) {
        priority_queue<int> q;
        int len = (nums.size() + 1) / 2;
        for (int i = 0; i < nums.size(); ++i) {
            if (q.size() < len) {
                q.push(nums[i]);
            }
            else {
                int tmp = q.top();
                if (nums[i] < tmp) {
                    q.pop();
                    q.push(nums[i]);
                }              
            }
        }
        return q.top();
    }
};